Matematika Diskret: Dasar Logika Kombinatorial

Bayangkan sebuah sistem di mana saat ini adalah satu-satunya yang penting—tidak ada memori masa lalu, tidak ada antisipasi masa depan. Ini adalah dunia dari logika kombinatorial. Di sini, rangkaian digital berperan sebagai penerjemah matematis instan, mengubah kombinasi tertentu dari sinyal masukan menjadi hasil unik tanpa kompleksitas loop umpan balik atau penyimpanan internal. Ini merupakan manifestasi fisik murni dari aljabar Boolean.

Arsitektur Logika Rekursif

Untuk membangun otak digital yang kompleks, kita harus terlebih dahulu menentukan tata bahasa dari bahasa mereka. Dalam aljabar Boolean apa pun $(S, +, \cdot, ', 0, 1)$, kita mendefinisikan ekspresi Boolean atas himpunan variabel $x_1, \dots, x_n$ melalui proses induksi struktural:

Kasus Dasar

1. Setiap konstanta $s \in S$ adalah ekspresi Boolean.
2. Setiap variabel $x_1, \dots, x_n$ adalah ekspresi Boolean.

Langkah Rekursif

Jika $X_1$ dan $X_2$ sudah merupakan ekspresi Boolean, maka berikut ini juga merupakan ekspresi yang valid:

$(X_1), \quad X_1', \quad X_1 + X_2, \quad X_1 \cdot X_2$

Prioritas dan Efisiensi

Dalam ketiadaan tanda kurung, kita mengikuti hierarki ketat untuk menghindari ambiguitas: Konjungsi ($\\land$) selalu memiliki prioritas lebih tinggi daripada Disjungsi ($\\lor$). Selain itu, untuk mengoptimalkan desain perangkat keras, kita menggunakan gerbang $n$-masukan. Alih-alih menghubungkan beberapa gerbang 2-masukan secara berurutan, kita mewakili $a_1 \vee a_2 \vee \dots \vee a_n$ sebagai satu unit logika tunggal, mengurangi keterlambatan propagasi dan menyederhanakan topologi rangkaian.

Prinsip Pemetaan Struktural

Setiap ekspresi aljabar adalah rancangan untuk rangkaian fisik. Pertimbangkan pembuatan untuk $(x_1 \wedge (\neg x_2 \vee x_3)) \vee x_2$:

Lapisan Dalam: Kita pertama kali mengisolasi $(\neg x_2 \vee x_3)$ dengan menggunakan gerbang NOT dan gerbang OR.
Lapisan Tengah: Hasil tersebut dimasukkan ke dalam gerbang AND bersamaan dengan sinyal dari $x_1$.
Lapisan Luar: Akhirnya, output AND dan jalur $x_2$ asli bertemu di gerbang OR akhir.

🎯 Prinsip Inti

Topologi rangkaian kombinatorial adalah refleksi fisik langsung dari urutan operasi ekspresi Boolean. Tidak ada memori, tidak ada umpan balik—hanya pemetaan murni dan instan.

PERTANYAAN 1

Apa yang mendefinisikan rangkaian kombinatorial?

Rangkaian di mana output bergantung pada keadaan masukan saat ini dan sebelumnya.

Rangkaian di mana output ditentukan secara unik oleh bit masukan saat ini dan tidak mengandung loop umpan balik.

Rangkaian yang menggunakan unit memori untuk menyimpan nilai Boolean antara.

Rangkaian yang hanya menggunakan gerbang NAND untuk mencapai kelengkapan fungsional.

PERTANYAAN 2

Nyatakan hukum asosiatif untuk $\wedge$ dan $\vee$ dalam aljabar Boolean.

$(a \lor b) \lor c = a \lor (b \lor c)$ dan $(a \land b) \land c = a \land (b \land c)$

$a \lor b = b \lor a$ dan $a \land b = b \land a$

$a \lor (b \land c) = (a \lor b) \land (a \lor c)$

$a \lor 0 = a$ dan $a \land 1 = a$

PERTANYAAN 3

Manakah dari berikut ini yang merupakan definisi standar operasi eksklusi-OR (XOR)?

$x \oplus y = x \land y$

$x \oplus y = (x \land \bar{y}) \lor (\bar{x} \land y)$

$x \oplus y = \overline{x \land y}$

$x \oplus y = x \lor y$

PERTANYAAN 4

Bagaimana Anda dapat merancang rangkaian menggunakan hanya gerbang NAND untuk menghitung hasil kali $xy$?

$(x \uparrow y) \uparrow (x \uparrow y)$

$x \uparrow y$

$(x \uparrow x) \uparrow (y \uparrow y)$

$x \uparrow (x \uparrow y)$

PERTANYAAN 5

Dalam rangkaian di mana $x_1$ dan $x_2$ masuk ke gerbang AND, diikuti langsung oleh gerbang NOT, apa ekspresi Boolean hasilnya?

$x_1 \land \bar{x_2}$

$\overline{x_1 \land x_2}$

$\bar{x_1} \land \bar{x_2}$

$x_1 \lor x_2$